from math import sqrt
from typing import *
from bisect import bisect_left, bisect_right


class Solution:

    def minimumCost(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)

        def palindromic_number():
            s = []
            for i in range(1, 10000):
                num = i
                p, q = num, num
                while num > 0:
                    g = num % 10
                    p = p * 10 + g
                    if q != num:
                        q = q * 10 + g
                    num //= 10
                s.append(q)
                s.append(p)
            s.append(1_000_000_001)
            s.sort()
            return s

        s = palindromic_number()

        r = bisect_left(s, nums[(n - 1) // 2])
        a, b = 0, 0
        for num in nums:
            a += abs(num - s[r])
            b += abs(num - s[r - 1])
        return min(a, b)


# s = Solution()
# print(
#     s.minimumCost(
#         [
#             1321,
#             7284,
#             9346,
#             9460,
#             7099,
#             2796,
#             5887,
#             9351,
#             2278,
#             7590,
#             7627,
#             1552,
#             5864,
#             7409,
#             9356,
#             8480,
#             2765,
#             8036,
#             8473,
#             5573,
#         ]
#     )
# )
# print(s.minimumCost([101, 104, 107, 126, 130]))
# [1, 2, 3, 4, 5]
# [10, 12, 13, 14, 15]
# [22, 33, 22, 33, 22]
# [311, 313, 320, 324]
# [301, 309, 312, 322]
# [101, 104, 107, 126, 130]


# print(sorted([522, 508, 984, 972, 959, 206, 412, 535, 530, 853, 605, 953, 102, 767]))
# for i in range(100):
#     print(i, i // 2, (i - 1) // 2)


def palindromic_number():
    s = []
    for i in range(1, 10001):
        num = i
        p, q = num, num
        while num > 0:
            g = num % 10
            if i <= 1000:
                p = p * 10 + g
            if q != num:
                q = q * 10 + g
            num //= 10
        s.append(q)
        if i <= 1000:
            s.append(p)
    s.append(1_000_000_001)
    return s


s = palindromic_number()

ss = sorted(s)
print(ss == s)


# pal = []
# base = 1
# while base <= 10000:
#     # 生成奇数长度回文数
#     for i in range(base, base * 10):
#         x = i
#         t = i // 10
#         while t:
#             x = x * 10 + t % 10
#             t //= 10
#         pal.append(x)
#     # 生成偶数长度回文数
#     if base <= 1000:
#         for i in range(base, base * 10):
#             x = t = i
#             while t:
#                 x = x * 10 + t % 10
#                 t //= 10
#             pal.append(x)
#     base *= 10
# pal.append(1_000_000_001)  # 哨兵，防止下面代码中的 i 下标越界

# print(pal == sorted(pal))
